In the last decades there has been an explosion in the usage of wireless communication for transmitting data between communicating stations or nodes. With this increase in wireless data communication, different types of wireless communications networks are developed that e.g. employ different media or medium access standards. A recently developed such medium access scheme is the Floor Acquisition Medium Access (FAMA) scheme. This medium access technique is, for example, implemented and used in IEEE 802.11 Wireless Local Area Networks (WLANs) and other contention-based networks. In these FAMA-based networks, the communication of data from a transmitting node or station to a receiving node temporarily blocks any transmission of other network nodes that potentially may overhear the data communication. This means that a node first have to verify the absence of other traffic before transmitting data on the shared physical medium.
Today, IEEE 802.11 enables single hop communication between nodes or stations in an independent basic service set mode. However, multihop support for the IEEE 802.11 and other contention-based networks is a desirable feature. This is because in a multihop network, nodes out of reach from each other may benefit from intermediately located nodes that can forward their messages from the source towards the destination. An additional benefit with multihop support is that by dividing a distance in multiple hops, each hop will experience significantly improved signal reception quality. Consequently, this can be exploited through usage of higher link rate that under certain conditions can reduce the end-to-end delay.
Traditionally, multihop networks have often been associated with so-called ad hoc networks where nodes are mostly mobile and no central coordinating infrastructure exists. However, the idea of multihop networking can also be applied when nodes are fixed. In addition, one can also envision central coordination, in particular when nodes are fixed and channels are robust. One may also envision hybrid networks involving wired links in addition to wireless links in multihop networks.
Routing, i.e. the act of moving information from a source to a destination via one or more intermediate nodes in a communication network, generally involves two basic tasks: determining suitable routing paths and transporting information through the network. In the context of the routing process, the first of these tasks is normally referred to as route determination and the latter of these tasks is often referred to as data or packet forwarding.
For route determination, a common approach is to span a so-called routing tree. The routing tree is normally calculated based on a shortest path algorithm, implying that the determined shortest paths from the various nodes in the tree to the destination node are so-called “least or minimum cost paths”. In practice, the tree may be continuously built and updated to manage mobility and changing link conditions.
When a particular node in the tree wants to send a packet in the subsequent packet forwarding process, the node is considered a source node, and the packet follows the determined routing path from the source to the destination. Different nodes may send packets to the same destination over time, hence different nodes will act as source nodes and send along their respective shortest path. In addition, as multiple destinations may exist, multiple trees may be generated, each rooted at a corresponding destination.
Packet forwarding is normally relatively straightforward, whereas path or route determination can be very complex.
Routing protocols generally use so-called routing metrics as a base for evaluating which path or route that will be the best for a given packet and thereby determining the optimal path to the destination. In the prior art, many different metrics have been used by the routing algorithms to determine the best, or at least a suitable route.
A classical wireline hop metric is unsuitable in a wireless environment, basically since it does not reflect the link quality dependency with respect to distance. An example of a wireline metric of less use in wireless situations, yet frequently encountered, is a simple hop count metric, where the link cost ΔCij from node vi to vj is defined as ΔCij=1.
Another metric that has been suggested in the research literature is based on the physical distance between two nodes, e.g. ΔCij=Distanceij.
A better example suited for a radio environment is to use the estimated average link rate and define link cost as the inverse of the average link rate, i.e. ΔCij=1/ rij, assuming rate adaptation capabilities. This metric can be seen in two ways. First, for a fixed sized packet, it strives to offer minimum delay paths (assuming that the queuing delay in the network is negligible). However, in the context of a multihop scheme with a fixed sized data phase (with varying number of packets in a data phase depending on rate adaptation) it offers the least time resource utilization along a path. The average rate based link metric can be estimated by the classical Shannon capacity:
                                                        r              _                        ij                    =                      B            ·                          E              ⁡                              (                                                      log                    2                                    ⁡                                      (                                          1                      +                                                                                                    G                            ij                                                    ⁢                                                      P                            i                                                                                                    σ                          N                          2                                                                                      )                                                  )                                                    ,                            (        1        )            where B is the bandwidth (may be neglected if only one common bandwidth is used in the whole system), E{ . . . } is the expectation value, Pi is the transmit power of node vi (which may be fixed or determined by some other mechanism), σN2 is the noise level (at node vj) and Gij is the average link gain. The term, σN2 could potentially also include average interference, modeled as complex Gaussian noise, apart from receiver noise.
Yet another example, suited for a radio environment, is the inverse of the average link gain, i.e. ΔCij=Gij−1. This metric provides large receiver SNR (Signal-to-Noise Ratio) values (with fixed power), and minimum power routes (with power control). This is not a bad metric, but it may lead to a situation where packets will experience long delays (mainly since it does not reflect the capacity of a link appropriately).
Using the Shannon capacity for the inverse gain metric case described above, it is seen that it corresponds to minimum power routing with a given target link rate rij(Target). The minimum power is then determined as:
                              P          i                =                              (                                          2                                                                            r                      _                                        ij                                          (                      Target                      )                                                        B                                            -              1                        )                    ⁢                                    σ              N              2                                      G              ij                                                          (        2        )            
Although the prior art link costs and routing metrics work fairly well for several wireless communications networks, they are not adapted to the specific characteristics of node blocking present in IEEE 802.11 and other contention- or FAMA-based communications networks.